package com.company.剑指offer每日刷题.普通版;

import java.util.*;

/**
 * 剑指 Offer 13. 机器人的运动范围
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
 * 它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，
 * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *
 *
 * 示例 1：
 *
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 *
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 * 0,0
 * 1,0
 * 2,0
 *
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 * */
public class MovingCount {
    /**
     * 方法：广度优先搜索
     * 思路：广度搜索
     * 注意：一定要仔细读题，k不满足的情况下，这个格子无法进入，意思是，这个格子无法被遍历。无法走到的格子，即使k是满足情况的，也无法计入结果之中。！
     * */
    public int movingCount(int m, int n, int k) {
        if(k == 0) return 1;
        boolean[][] visit = new boolean[m][n];
        int res = 0;
        byte[][] direct = new byte[][]{{0,1},{1,0}};
        Queue<Integer[]> queue = new LinkedList<>();
        queue.offer(new Integer[]{0,0});
        visit[0][0] = true;
        while(!queue.isEmpty()){
            Integer[] node = queue.poll();
            for (int i = 0; i < 2; i++) {
                int ii = node[0] + direct[i][0];
                int jj = node[1] + direct[i][1];
                if(ii >= 0 && ii < m  && jj >=0 && jj < n && !visit[ii][jj] && getSum(ii) + getSum(jj) <= k){
                    queue.offer(new Integer[]{ii,jj});
                    visit[ii][jj] = true;
                }
            }
            res ++;
        }
        return res;
    }
    //获取一个数字的所有位数之和
    private int getSum(int value){
        int res = 0;
        while(value != 0){
            res += value % 10;
            value /= 10;
        }
        return res;
    }

    public static void main(String[] args) {
//        MovingCount obj = new MovingCount();
//        int res = obj.movingCount(16, 8, 4);
//        System.out.println(res);
        int[] arr = new int[]{1,0,7,6,5,4,9,3};
        int[] index = new int[]{0,4,3,1,2,0,5,4,3,6,7};
        String tel = "";
        for (int i :index   ) {
            tel += arr[i];
        }
        System.out.println(tel);
    }
}
